기수정렬
자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다.
각 데이터를 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도를 가진다.
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
void radixSort(int *a, int n){
int res[MAX], maxValue=0;
int exp=1;
for(int i=0;i<n;i++){
if(a[i]>maxValue)maxValue=a[i];
}
while(maxValue/exp>0){
int bucket[10]={0};
for(int i=0;i<n;i++)bucket[a[i]/exp%10]++;
for(int i=1;i<10;i++)bucket[i]+=bucket[i-1];
for(int i=n-1;i>=0;i--){
res[--bucket[a[i]/exp%10]]=a[i];
}
for(int i=0;i<n;i++)a[i]=res[i];
exp*=10;
}
}
int main(void){
int a[MAX];
int i,n;
scanf("%d", &n);
for(int i=0;i<n;i++){
scanf("%d", &a[i]);
}
radixSort(a,n);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
system("pause");
}
기수 정렬은 계수 정렬보다 약간 더 느리지만, 숫자가 큰 상황에서도 사용할 수 있다.